package Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 654.最大二叉树
 * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 * 1. 创建一个根节点，其值为 nums 中的最大值。
 * 2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * 3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 返回 nums 构建的 最大二叉树 。
 */
public class constructMaximumBinaryTree {

    /**
     * 一刷
     * 一刷的思路写的比较复杂，建议看二刷的写法
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) return null;

        int max = findMax(nums);
        List<int[]> splitnums = splitnums(nums, max);
        TreeNode root = new TreeNode(max);
        root.left = constructMaximumBinaryTree(splitnums.get(0));
        root.right = constructMaximumBinaryTree(splitnums.get(1));

        return root;
    }

    public static int findMax(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int max = nums[0];
        if (nums.length == 1) return max;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > max) max = nums[i];
        }
        return max;
    }

    public static List<int[]> splitnums(int[] nums, int max) {
        List<int[]> res = new ArrayList<>();
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == max) {
                index = i;
            }
        }
        int[] left = new int[index];
        int[] right = new int[nums.length - index - 1];
        for (int i = 0; i < left.length; i++) {
            left[i] = nums[i];
        }
        for (int i = 0; i < right.length; i++) {
            right[i] = nums[index + i + 1];
        }
        res.add(left);
        res.add(right);
        return res;
    }

    /**
     * 二刷
     */
    public static TreeNode constructMaximumBinaryTree2(int[] nums) {
        if (nums.length == 0 || nums == null) {
            return null;
        }
        int max = getMax(nums);
        int index = getindex(nums, max);

        TreeNode root = new TreeNode(max);
        root.left = constructMaximumBinaryTree2(Arrays.copyOfRange(nums, 0, index));
        root.right = constructMaximumBinaryTree2(Arrays.copyOfRange(nums, index + 1, nums.length));
        return root;
    }

    public static int getMax(int[] nums) {
        int max = -1;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, nums[i]);
        }
        return max;
    }

    public static int getindex(int[] nums, int max) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == max) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 6, 0, 5};
        constructMaximumBinaryTree2(nums);
    }

}
